{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Search Tree FAQ Summary\n",
    "\n",
    "[@mjd507][1] ｜ [WeChat Channel（简体中文版）][2]\n",
    "\n",
    "![Logo](images/BST-1.png)\n",
    "\n",
    "[1]: https://github.com/mjd507\n",
    "[2]: https://mp.weixin.qq.com/s/WL-tJvWO5UNNm_WKCr7IVw"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I wrote a summary of the [Binary Tree FAQ](Binary_Tree.ipynb) before, this time I compiled the *binary search tree*.\n",
    "\n",
    "The *binary search tree* has one more feature on the basis of the *binary tree*:\n",
    "\n",
    "- For a node, the value of its left subnode is less than that of the current node. Also, the value of its right subnode is grater than that of the current node.\n",
    "\n",
    "The *binary search tree* is used because its search effeciency - which can be reduced to  $O(\\log n)$.\n",
    "\n",
    "Here I put four classic subject together and we can take the time to do, in order to deepen management solution.\n",
    "\n",
    "- [Lookup nodes in a binary search tree](#Find-node)\n",
    "- [Insert nodes in a binary search tree](#Insert-node)\n",
    "- [Delete nodes in a binary search tree](#Delete-node)\n",
    "- [The Kth largest element in the data stream](#The-Kth-largest-element-in-the-data-stream)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find node\n",
    "\n",
    "> Given a binary search tree and a target value, find the node in the binary search tree which its value is equal to the target value.\n",
    ">\n",
    "> Returns the node and its subtree, or `None` if the node does not exist.\n",
    ">\n",
    "> For example: Given a target value of $2$ and the following binary search tree:\n",
    ">\n",
    "> ```text\n",
    ">     4\n",
    ">    / \\\n",
    ">   2   6\n",
    ">  / \\\n",
    "> 1   3\n",
    "> ```\n",
    ">\n",
    "> Return to this subtree:\n",
    "> ```text\n",
    ">   2\n",
    ">  / \\\n",
    "> 1   3\n",
    "> ```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def search(root: dict, value: int) -> dict:\n",
    "    if root is None or root['value'] == value:\n",
    "        return root\n",
    "    elif root['value'] > value:\n",
    "        return search(root['left'], value)\n",
    "    else:\n",
    "        return search(root['right'], value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Insert node\n",
    "\n",
    "> Given a binary search tree and a value, insert the value into the binary search tree and keep the tree still a binary search tree.\n",
    ">\n",
    "> For example, given a node value of 5 and a binary search tree below:\n",
    "> ```text\n",
    ">     4\n",
    ">    / \\\n",
    ">   2   7\n",
    ">  / \\\n",
    "> 1   3\n",
    "> ```\n",
    ">\n",
    "> Return to the following tree:\n",
    "> ```text\n",
    ">      4\n",
    ">    /   \\\n",
    ">   2     7\n",
    ">  / \\   /\n",
    "> 1   3 5\n",
    "> ```\n",
    "\n",
    "There provides two methods of recursion and iteration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_recursively(tree: dict, value: int) -> dict:\n",
    "    if tree is None:\n",
    "        return {'value': value}\n",
    "    if tree['value'] > value:\n",
    "        tree['left'] = tree.setdefault('left')\n",
    "        tree['left'] = insert_recursively(tree['left'], value)\n",
    "    else:\n",
    "        tree['right'] = tree.setdefault('right')\n",
    "        tree['right'] = insert_recursively(tree['right'], value)\n",
    "    return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_iteratively(tree: dict, value: int) -> dict:\n",
    "    new_node = {'value': 5}\n",
    "    if tree is None:\n",
    "        return new_node\n",
    "    dummy = tree\n",
    "    previous = None\n",
    "    while tree is not None:\n",
    "        if tree['value'] > value:\n",
    "            (previous, tree) = (tree, tree.setdefault('left'))\n",
    "        else:\n",
    "            (previous, tree) = (tree, tree.setdefault('right'))\n",
    "    if previous['value'] > value:\n",
    "        previous['left'] = new_node\n",
    "    else:\n",
    "        previous['right'] = new_node\n",
    "    return dummy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Delete node\n",
    "\n",
    "> Delete a node in the binary search tree and keep the tree still a binary search tree.\n",
    ">\n",
    "> For example, given a node value of 3 and a binary search tree below:\n",
    "> ```text\n",
    ">     5\n",
    ">    / \\\n",
    ">   3   6\n",
    ">  / \\   \\\n",
    "> 2   4   7\n",
    "> ```\n",
    ">\n",
    "> <br>\n",
    ">\n",
    "> You should return the following binary tree:\n",
    "> ```text\n",
    ">     5                5\n",
    ">    / \\              / \\\n",
    ">   4   6      or    2   6\n",
    ">  /     \\            \\   \\\n",
    "> 2       7            4   7\n",
    "> ```\n",
    "\n",
    "Deleting a node is more complicated. Assuming that the node to be deleted is $z$, there are three cases:\n",
    "1. If $z$ has no child nodes, simply delete it.\n",
    "2. If $z$ has only one child, then raise the child to the position of z.\n",
    "3. If $z$ has two children, use the successor $y$ of $z$ to occupy the position of $z$.\n",
    "    \n",
    "    The successor $y$ of $z$ must be in the right subtree of $z$, because the right child of $z$ is not empty.\n",
    "    \n",
    "    $y$ also distinguish whether it is the direct right child of node $z$.\n",
    "\n",
    "Here is [an article](http://www.algolist.net/Data_structures/Binary_search_tree/Removal) dedicated to the binary search tree deletion node.\n",
    "\n",
    "The following is implemented according to its explanation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BSTNode:\n",
    "    def __init__(self, value: int, left=None, right=None):\n",
    "        self.value = value\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "    def minValue(self) -> int:\n",
    "        if self.left is None:\n",
    "            return self.value\n",
    "        else:\n",
    "            return self.left.minValue()\n",
    "\n",
    "    def remove(self, value: int, parent) -> bool:\n",
    "        if value < self.value:\n",
    "            if self.left is not None:\n",
    "                return self.left.remove(value, self)\n",
    "            else:\n",
    "                return False\n",
    "        elif value > self.value:\n",
    "            if self.right:\n",
    "                return self.right.remove(value, self)\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            # It has both left and right subtree.\n",
    "            if self.left and self.right:\n",
    "                self.value = self.right.minValue()\n",
    "                self.right.remove(self.value, self)\n",
    "            # It has only left subtree.\n",
    "            elif parent.left == self:\n",
    "                parent.left = (self.left if self.left else self.right)\n",
    "            elif parent.right == self:\n",
    "                parent.right = (self.left if self.left else self.right)\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete(root: BSTNode, value: int) -> BSTNode:\n",
    "    if root is None:\n",
    "        return False\n",
    "    if root.value == value:\n",
    "        dummy_root = BSTNode(0, root, None)\n",
    "        success = root.remove(value, dummy_root)\n",
    "        root = dummy_root.left\n",
    "        return success\n",
    "    else:\n",
    "        return root.remove(value, None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Kth largest element in the data stream\n",
    "\n",
    "> Design a class to find the kth largest element in the data stream.\n",
    ">\n",
    "> Ps: You only need to rank the element with the kth largest, and you don't need to filter the same element.\n",
    ">\n",
    "> The KthLargest class needs to have a constructor that accepts an integer `k` and an array of integers `arr` (initial elements). It also needs an `add(val)` method, adding one element at a time, returning the latest kth largest element.\n",
    ">\n",
    "> For example:\n",
    ">\n",
    "> ```python\n",
    "> kthLargest = KthLargest(3, arr)\n",
    "> # returns 4\n",
    "> kthLargest.add(3)\n",
    "> # returns 5\n",
    "> kthLargest.add(5)\n",
    "> # returns 5\n",
    "> kthLargest.add(10)\n",
    "> # returns 8\n",
    "> kthLargest.add(9)\n",
    "> # returns 8\n",
    "> kthLargest.add(4)\n",
    "> ```\n",
    ">\n",
    "> It can be assumed that the `arr` length is $\\geq k-1$ and $k \\geq 1$.\n",
    "\n",
    "The core of this problem is solved by a minimum heap. First, construct a minimum heap when initializing. If the elements in the heap exceed `k`, directly pop out these smaller values, because these values will not play any role but only increase the complexity of the heap operation.\n",
    "\n",
    "Python3 has a native implementation of the largest heap minimum heap. It is the core of this question. I recommend you write it yourself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "\n",
    "class KthLargest:\n",
    "    def __init__(self, k: int, arr: list):\n",
    "        self.k = k\n",
    "        self.heap = arr\n",
    "        heapq.heapify(self.heap)\n",
    "\n",
    "    def add(self, val: int) -> int:\n",
    "        heapq.heappush(self.heap, val)\n",
    "        return heapq.nlargest(self.k, self.heap)[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "largest = KthLargest(3, [4, 5, 8, 2])\n",
    "largest.add(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "largest.add(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "largest.add(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "largest.add(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "largest.add(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Afterword\n",
    "\n",
    "I have maintained an algorithmic communication group. and the atmosphere is very good. If you want to join, scan the following QR code to add my personal WeChat account and I will pull you in.\n",
    "\n",
    "![Wechat Account QR code](images/BST-2.jpg)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
